#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#define N 10

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int cnt = 0, sum = 0;
        unordered_map<int, int> hash;
        hash.insert(make_pair<int, int>(0, 1));

        for (int i = 0; i < nums.size(); i++)
        {
            sum = sum + nums[i];
            if (hash.count(sum - k))
                cnt += hash[sum - k];

            hash[sum]++;
        }

        return cnt;
    }



    //     vector<int> dp(nums.size(), nums[0]);
    //     for (int i = 1; i < dp.size(); i++)
    //         dp[i]  = dp[i - 1] + nums[i];

    //     int cnt = 0;
    //     for (int i = 0; i < dp.size(); i++)
    //     {
    //         if (k == dp[i])
    //             cnt++;

    //         for (int j = 0; j < i; j++)
    //         {
    //             if (dp[i] - dp[j] == k)
    //                 cnt++;
    //         }
    //     }

    //     return cnt;
    // }
};